package geeksforgeeks.trees;

public class TreeTraversals {

	public static void main(String[] args) {
		Node root = new Node(5);

		root.left = new Node(3);
		root.right = new Node(8);
		root.left.left = new Node(1);
		root.left.right = new Node(4);
		
		System.out.println("Pre Order Traversal");
		printPreOrder(root);
		
		System.out.println("In Order Traversal");
		printInOrder(root);
		
		System.out.println("Post Order Traversal");
		printPostOrder(root);
		
		System.out.println("Reverse In Order");
		printReverseInOrder(root);

	}
	
	private static void printReverseInOrder(Node root) {
		if(root == null)
			return;
		printReverseInOrder(root.right);
		System.out.println(root.data);
		printReverseInOrder(root.left);
		
	}

	private static void printPostOrder(Node root)
	{
		if(root == null) return;
		
		printPostOrder(root.left);
		printPostOrder(root.right);
		System.out.println(root.data);
	}
	

	public static void printInOrder(Node root) {
		if(root == null)
			return;
		
		printInOrder(root.left);
		System.out.println(root.data);
		printInOrder(root.right);
		
	}


	public static void printPreOrder(Node root) {
		if(root == null)
			return;
		
		System.out.println(root.data);
		if(root.left != null)
			printPreOrder(root.left);
		if(root.right != null)
			printPreOrder(root.right);
		
	}
	
	


	static class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {
			this.data = data;
			this.left = this.right = null;
		}
		
		public String toString()
		{
			return String.valueOf(data);
		}
	}

}
